\documentclass{beamer}
\usepackage{ctex}
\usepackage{graphicx}
\usetheme{Madrid}
    
\author{uncle-lu}
\institute{乌鲁木齐市第一中学}
\title{Union-Find Set}
\date{\today}

\begin{document}
    \frame{\titlepage}

    \begin{frame}\frametitle{简单问题}
        需要你写一个数据结构,支持以下两种操作:
        \begin{itemize}
            \item 询问两个元素是否在一个集合.
            \item 将两个元素所在的集合合并.
        \end{itemize}
    \end{frame}

    \begin{frame}\frametitle{Disjoint-set Data Structure}
        \textbf{并查集}:一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题.

        \pause 

        \begin{center}
        极低的编程复杂度，极佳的时空复杂度，极其惹人喜爱。
        \end{center}

        \pause

        它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系.
        
        \pause

        \begin{itemize}
            \item Union : 将两个子集合并成同一个集合
            \item Find : 确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集
        \end{itemize}

        \pause
        
        我们用一个代表(Representative)来标识每个集合.我们不关心哪个元素被作为代表.我们仅仅关系2次查询动态集合的代表中的关系.

    \end{frame}

    \begin{frame}\frametitle{实现及其优化}
        基本实现.(Disjoint-set Forest方法)
        \begin{figure}[htbp]
            \centering
            \includegraphics[width=1\textwidth]{First.png}
        \end{figure}
    \end{frame}
    
    \begin{frame}{实现及其优化}
        改进运行时间的启发式策略:
        
        \begin{itemize}
            \item 按秩合并(union by rank)
                
                将较少结点的树的根合并到较多结点的树的根.
            \item 路径压缩(path compression)
        \end{itemize}
        
        路径压缩优化:
        \begin{figure}[htbp]
            \centering
            \includegraphics[width=1\textwidth]{Second.png}
        \end{figure}
        
    \end{frame}

    \begin{frame}\frametitle{实现及其优化}
        带权并查集:
        \begin{figure}[htbp]
            \centering
            \includegraphics[width=1\textwidth]{Third.png}
        \end{figure}

        注意:带权并查集因题而异.没有固定的写法.此写法仅是抛砖引玉.
    \end{frame}

    \begin{frame}\frametitle{关于复杂度}

    同时使用路径压缩、按秩合（rank）并优化的程序每个操作的平均时间仅为 ${\displaystyle O(\alpha (n))}$，其中 ${\displaystyle \alpha (n)} $ 是 ${\displaystyle n=f(x)=A(x,x)} $ 的反函数，${\displaystyle A} $ 是急速增加的阿克曼函数。因为 ${\displaystyle \alpha (n)}$ 是其反函数，故 ${\displaystyle \alpha (n)} $ 在 ${\displaystyle n} $ 十分巨大时还是小于 5。因此，平均运行时间是一个极小的常数。实际上，这是渐近最优算法：Fredman 和 Saks 在 1989 年解释了 ${\displaystyle \Omega (\alpha (n))} $ 的平均时间内可以获得任何并查集。

    摘自维基百科.

    \end{frame}

    \begin{frame}\frametitle{常见作用}
        \begin{itemize}
            \item 维护连通性 如: kruskal算法
            \item 建立虚点，维护相对性 
            \item 保留集合元素之间的相互关系(特殊路径压缩)
            \item 维护特殊数据值的关系.
            \item 缩点?
        \end{itemize}
    \end{frame}

    \begin{frame}

        \begin{center}
           \Huge{\textbf{杂题讨论+选讲}}

        \end{center}

        \begin{center}
            注:题目不按难度排序,仅按讲题人心情.
        \end{center}

    \end{frame}

    \begin{frame}\frametitle{Problem +1s}
        \begin{beamerboxesrounded}[shadow=true]{Color the Axis}
            在一条数轴上有 N 个点，分别是 1 ～ N 。一开始所有的点都被染成黑色。接着我们进行 M 次操作，第 i 次操作将 [Li , Ri ] 这些点染成白色。请输出每个操作执行后剩余黑色点的个数。
        \end{beamerboxesrounded}

        $1 <= Li <= Ri <= N <= 200000$

        $  1 <= M <= 200000 $
    \end{frame}

    \begin{frame}\frametitle{Solution}
        算法一:线段树.

        \pause

        算法二:

        暴力并查集.

        一个点被染过之后就把这个点的 Father 指针指向后面的点。

        代码实现:http://paste.ubuntu.com/25572735/
    \end{frame}

    \begin{frame}\frametitle{Problem +2s}
        \begin{beamerboxesrounded}[shadow=true]{狡猾的商人}
            有一个序列.但是你不知道这个序列中的数.给你序列中很多段区间的区间和.问这个序列存不存在.
        \end{beamerboxesrounded}
        $n<100$

        $m<1000$
    \end{frame}

    \begin{frame}\frametitle{Solution}
        算法一:

        带权并查集.
        \pause

        区间和我们可以转化为前缀和相减.

        \pause

        其中设$V[x]$为x这个点 到它所在联通块的距离.

        对于任意给你的区间$(x,y)$;

        当x,y都在同一集合里我们只需要判断$V[y]-V[x-1]?=Val$;

        当不在同一集合:
       
        $p=Find(x-1),q=Find(y),V[p]=V[y]-V[x-1]-Val$
        
        这样就可以并查集合并了.

        代码实现:http://uncle-lu.org/archives/426
        \pause

        算法二:差分约束.

        From:BZOJ1202
    \end{frame}

    \begin{frame}\frametitle{Problem +3s}
		\begin{beamerboxesrounded}[shadow=true]{关押罪犯}
			给你一个无向图.让你把无向图中的点分成两个集合.集合之间的边取消.要求两个集合中边权最大值最小.求该最大值.
		\end{beamerboxesrounded}
		数据范围:
		
		对于30\%的数据有$N \leq 15$。
		
		对于70\%的数据有$N \leq 2000，M \leq 50000$
		
		对于100\%的数据有$N \leq 20000，M \leq 100000$
	\end{frame}

	\begin{frame}\frametitle{Solution}
		\begin{itemize}
			\item 算法一:

			用并查集.先按照边权排序.

			如果两点在同一个集合则输出.

			否则将合并到敌人的集合中.

			代码实现:http://paste.ubuntu.com/25494722/

			\pause

			\item 算法二:

			二分答案+染色.

			我们可以轻易的发现.一个很难发现的现象.

			我们枚举出来的最大值.比最大值大的边都链接在两个集合中,我们只需要判断是否是二分图就可以判断答案的正确性.

			代码实现:http://paste.ubuntu.com/25494724/

			\item From:NOIP2010.
		\end{itemize}
    \end{frame}
    
    \begin{frame}\frametitle{Problem +4s}
        \begin{beamerboxesrounded}[shadow=true]{CLO}
            给你n个点和m条双向边，问能否将其中的某些边改成有向边，使得只考虑有向边的情况下每个点的入度都为1.
        \end{beamerboxesrounded}

        $1 \leq n \leq 100000$
        
        $1 \leq m \leq 200000$
    \end{frame}

    \begin{frame}\frametitle{Solution}
        对于任意的联通块,只要有环,则可以将这个联通块链接方式变成环中互连,环中向环外连的方式。

        所以我们用并查集找环就好.

        代码实现:http://paste.ubuntu.com/25576832/
        
        From:BZOJ1116[POI2008]
    \end{frame}

    \begin{frame}\frametitle{Problem +5s}
        \begin{beamerboxesrounded}[shadow=true]{游戏}
            有n个元素.每个元素都有两个值.但是每次使用一个元素的时候只能得到其中一个值.问.使用这些元素.最多能得到多少个从1开始的连续的值.
        \end{beamerboxesrounded}
        $n \leq 1000000$
    \end{frame}

    \begin{frame}\frametitle{Solution}
        算法一:

        二分图匹配.

        每个数值和武器连边,建图跑最大匹配即可.

        \pause

        算法二:

        将一个元素$(x,y)$看成一条链接x,y的无向边.

        \pause

        我们轻而易举的可以发现:

        在一个联通块内:
        \begin{itemize}
            \item 如果有一个环则这个联通块内的所有点均可以被取到.
            \item 如果为一颗有n个点树.则最多可以取n-1个点.
        \end{itemize}
        对于一棵树.我们贪心最大点那个点取不到.

        之后用并查集维护联通块,记录是否为环,记录树上最大的点即可.

        代码实现:http://paste.ubuntu.com/25577636/

        From:BZOJ1854
        
    \end{frame}

    \begin{frame}\frametitle{Problem +6s}
        \begin{beamerboxesrounded}[shadow=true]{旅行}
        有N个点,m条双向边,每一条边有一个权值.之后有q次询问.每次询问给一个值A.问.有多少个点对(x,y)使得存在一条x到y的路径上的最大值小于A.
        
        可能有重边和自环.
        \end{beamerboxesrounded}
        $n \leq 100000$
        
        $m \leq 200000$
        
        $q \leq 200000$
        
        其他权值不超过$1e9$
    \end{frame}

    \begin{frame}\frametitle{Solution}
        我们可以首先将每条边排序.
        
        然后在图中依次加入边.用并查集来维护联通性.顺带计算答案(乘法原理).这样我们就有一个由边权大小的答案表.之后二分查找答案即可.
        
        代码实现:http://paste.ubuntu.com/25584280/
        
        From:TYVJ1460
        
    \end{frame}
    
    \begin{frame}{Problem +7s}
        \begin{beamerboxesrounded}[shadow=true]{星球大战starwar}
            给定一个无向图,求联通块个数,以及k次每次摧毁一个点后的联通块个数
        \end{beamerboxesrounded}
        $1 \leq m \leq 200000$
        
        $1 \leq  n \leq  2m$
    \end{frame}
    
    \begin{frame}{Solution}
    逆向思维.
    
    倒着做.
    
    代码实现:http://uncle-lu.org/archives/56
    
    From:BZOJ1015
    \end{frame}
    
    \begin{frame}\frametitle{Problem +8s}
    
        \begin{beamerboxesrounded}[shadow=true]{思考题}
            一个人有很多的影子，新的旧的，他们不断消失重来。学者的影子在他苍白色的精神图
景里成为了 $n$ 个黑色的点，他们伸长的触手交叉形成了一颗黑色的树。假使每个影子点
拥有一个权值 $d_i$ ，黑色的树边也有一个权值 $W_i$，对于一条黑色树的路径，令路径上所
有影子点权值 $d_i$ 的最小值为 $min(d)$，路径上所有树边权值 $W_i$ 的总和为 $Sum_w$，则该
条路径的总权值为 $min(d)$ * $Sum_w$。路径的起点和终点可以是黑色树中的任意影子点，
且路径中不能出现重复的影子点。

现在学者需要知道这棵黑色树里所有路径总权值中的最大值为多少?
        \end{beamerboxesrounded}
        $1\leq n \leq 10^5$
        
        $1\leq di \leq 10^9$
        
        $1\leq wi \leq 10^9$
    \end{frame}
    
    \begin{frame}{Solution}
    将所有点按照权值从大到小排序，对于将当前点和与其相连的所有点依次合
并到一个集合中。

并查集需要维护当前集合中的最长路径长度和对应的两个端点。

在合并两个集合后，最终集合的最长路一定只有两类情况：

一类是其中一个集合的最长路，一共有 2 种；

一类是由两个集合的最长路的端点互相连接而成，一共有 2×2=4种。

需要用到最近公共祖先的算法预处理求两点在树上的距离，离线处理即可。

每次合并并查集之后用当前点的权值乘以最长路的总长度来更新最优结果即可。

即使这个点不在当前合并后的集合的最长路上也是没有问题的，因为如果这样的话，必然已经在之前得到了对应的结果，这次合并不会对最终结果产生影响。
    \end{frame}
    
    
    
\end{document}